{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# 推荐系统冷启动问题\n",
    "推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣，因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。对于很多做纯粹推荐系统的网站，或者很多在开始阶段就希望有个性化推荐应用的网站来说，如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，这就是 **冷启动（cold start）** 的问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org632d68b\"></a>\n",
    "## 冷启动问题简介\n",
    "\n",
    "冷启动问题主要分3类：\n",
    "\n",
    "-   **用户冷启动**\n",
    "\n",
    "    主要解决如何给新用户做个性化推荐的问题。（缺少新用户的行为数据）\n",
    "\n",
    "-   **物品冷启动**\n",
    "\n",
    "    主要解决如何将新的物品推荐给可能对它感兴趣的用户这一问题。\n",
    "\n",
    "-   **系统冷启动**\n",
    "\n",
    "    主要解决如何在一个新开发的网站上（还没有用户，也没有用户行为，只有一些物品的信息）设计个性化推荐系统，从而在网站刚发布时就让用户体验到个性化推荐服务这一问题。\n",
    "\n",
    "对于上述3种不同的冷启动问题，一般可参考如下解决方案：\n",
    "\n",
    "-   提供非个性化的推荐\n",
    "\n",
    "    最简单例子就是热门排行榜，等到用户数据收集到一定的时候，再切换为个性化推荐。\n",
    "\n",
    "-   利用用户注册时提供的年龄、性别等数据做粗粒度的个性化。\n",
    "\n",
    "-   利用用户的社交网络账号登录（需用户授权），导入用户在社交网站上的好友信息，然后给用户推荐其好友喜欢的物品。\n",
    "\n",
    "-   要求用户在登录时对一些物品进行反馈，收集用户对这些物品的兴趣信息，然后给用户推荐那些和这些物品相似的物品。\n",
    "\n",
    "-   对于新加入的物品，可利用内容信息，将其推荐给喜欢过和它们相似的物品的用户。\n",
    "\n",
    "-   引入专家的知识，通过一定的高效方式迅速建立起物品的相关度表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org6541e05\"></a>\n",
    "## 利用用户注册信息\n",
    "用户的注册信息分3种：\n",
    "\n",
    "-   **人口统计学信息:** 包括用户的年龄、性别、职业、民族、学历和居住地。\n",
    "-   **用户兴趣的描述:** 有一些网站会让用户用文字描述他们的兴趣。\n",
    "-   **从其他网站导入的用户站外行为数据:** 比如用户通过豆瓣、新浪微博的账号登录，就可以在得到用户同意的情况下获取用户在豆瓣或者新浪微博的一些行为数据和社交网络数据。\n",
    "\n",
    "基于注册信息的个性化推荐流程：\n",
    "\n",
    "1.  获取用户的注册信息；\n",
    "2.  根据用户的注册信息对用户分类；\n",
    "3.  给用户推荐他所属分类中用户喜欢的物品。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org23d28c0\"></a>\n",
    "\n",
    "## 选择合适的物品启动用户的兴趣\n",
    "\n",
    "一般来说，能够用来启动用户兴趣的物品需要具有以下特点。\n",
    "\n",
    "-   比较热门\n",
    "\n",
    "    如果要让用户对一个物品进行反馈，前提是用户知道这个物品是什么东西。以电影为例，如果一开始让用户进行反馈的电影都很冷门，而用户不知道这些电影的情节和内容，也就无法对它们做出准确的反馈。\n",
    "\n",
    "-   具有代表性和区分性\n",
    "\n",
    "    启动用户兴趣的物品不能是大众化或老少咸宜的，因为这样的物品对用户的兴趣没有区分性。还以电影为例，用一部票房很高且广受欢迎的电影做启动物品，可以想象的到的是几乎所有用户都会喜欢这部电影，因而无法区分用户个性化的兴趣。\n",
    "\n",
    "-   启动物品集合需要有多样性\n",
    "\n",
    "    在冷启动时，我们不知道用户的兴趣，而用户兴趣的可能性非常多，为了匹配多样的兴趣，需要提供具有很高覆盖率的启动物品集合，这些物品能覆盖几乎所有主流的用户兴趣。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org3660159\"></a>\n",
    "## 利用物品的内容信息\n",
    "\n",
    "物品冷启动需要解决的问题是如何将新加入的物品推荐给对它感兴趣的用户。\n",
    "\n",
    "对于UserCF，可以考虑利用物品的内容信息，将新物品先投放给曾经喜欢过和它内容相似的其他物品的用户。只要有一小部分人能够发现并喜欢新的物品，UserCF算法就能将这些物品扩散到更多的用户中。\n",
    "\n",
    "对于ItemCF，解决物品冷启动问题的办法是频繁更新物品相似度表，但基于用户行为计算物品相似度是非常耗时的事情，主要原因是用户行为日志非常庞大。而且，新物品如果不展示给用户，用户就无法对它产生行为，通过行为日志计算是计算不出包含新物品的相关矩阵的。 **只能利用物品的内容信息计算物品相关表，并且频繁地更新相关表（比如半小时计算一次）。**\n",
    "\n",
    "**物品的内容信息多种多样，不同类型的物品有不同的内容信息。**\n",
    "\n",
    "下面是常见物品的常用内容信息：\n",
    "\n",
    "| 物品 | 信息                     |\n",
    "|------|--------------------------|\n",
    "| 图书 | 标题、作者、出版社、出版年代、丛书名、目录、正文 |\n",
    "| 论文 | 标题、作者、作者单位、关键字、分类、摘要、正文 |\n",
    "| 电影 | 标题、导演、演员、编剧、类别、剧情简介、发行公司 |\n",
    "| 新闻 | 标题、正文、来源、作者   |\n",
    "| 微博 | 作者、内容、评论         |\n",
    "\n",
    "一般来说，物品的内容可以通过向量空间模型<sup><a id=\"fnr.1\" class=\"footref\" href=\"#fn.1\">1</a></sup>表示，该模型会将物品表示成一个 **关键词** 向量。\n",
    "\n",
    "如果物品的内容是一些诸如导演、演员等实体的话，可以直接将这些实体作为关键词。\n",
    "\n",
    "如果内容是文本的形式，则需要引入一些理解自然语言的技术 **抽取关键词** 。\n",
    "\n",
    "下图展示了从文本生成关键词向量的主要步骤：\n",
    "\n",
    "![img](../recsys_images/keywords_generation.png \"关键词向量的生成过程\")\n",
    "\n",
    "对于中文，首先要对文本进行分词<sup><a id=\"fnr.2\" class=\"footref\" href=\"#fn.2\">2</a></sup>，将字流变成词流，然后从词流中检测出命名实体（如人名、地名、组织名等），这些实体和一些其他重要的词将组成关键词集合，最后对关键词进行排名，计算每个关键词的权重，从而生成关键词向量。\n",
    "\n",
    "对物品 $d$ ，它的内容表示成一个关键词向量如下：\n",
    "\n",
    "\\begin{equation}\n",
    "d_i = \\{(e_1,w_1),(e_2,w_2),\\cdot\\cdot\\cdot\\} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "其中，$e_i$ 就是关键词，$w_i$ 是关键词对应的权重。\n",
    "\n",
    "如果物品是文本，可以用信息检索领域著名的TF-IDF（Term Frequency-Inverse Document Frequency，词频—逆文档频率。如果某个词比较少见，但是它在一篇文章中多次出现，那么它很可能就反映了这篇文章的特性，可将其定为关键词。）<sup><a id=\"fnr.3\" class=\"footref\" href=\"#fn.3\">3</a></sup>公式计算词的权重：\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "& tf(t,d) = \\frac{f_{t,d}}{\\sum_{t' \\in d}{f_{t',d}}} \\\\\n",
    "& idf(t,D) = \\log{\\frac{N}{1 + |\\{d \\in D: t \\in d \\}|}} \\\\\n",
    "& tfidf(t,d,D) = tf(t,d) \\cdot idf(t,D) \\\\\n",
    "\\end{split} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "$d$ 表示一篇文章， $D$ 表示整个文件集合， $N$ 表示文件集合中的文件总数， $|\\{d \\in D: t \\in d \\}|$ 表示文件集合中包含词语 $t$ 的文件数量。某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。\n",
    "\n",
    "\\begin{equation}\n",
    "w_i = tfidf(e_i,d,D) \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "如果物品是电影，可以根据演员在剧中的重要程度赋予他们权重。\n",
    "\n",
    "向量空间模型的优点是简单，缺点是丢失了一些信息，比如关键词之间的关系信息。不过在绝大多数应用中，向量空间模型对于文本的分类、聚类、相似度计算已经可以给出令人满意的结果。\n",
    "\n",
    "给定物品内容的关键词向量后，物品的内容相似度可以通过向量之间的余弦相似度计算：\n",
    "\n",
    "\\begin{equation}\n",
    "w_{ij} = \\frac{d_i \\cdot d_j}{\\sqrt{\\|d_i\\| \\|d_j\\|}} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "在实际应用中，可以首先通过建立关键词——物品的倒排表来计算物品之间的内容相似度，下面是计算的代码：\n",
    "\n",
    "```python\n",
    "def calculate_similarity(entity_items):\n",
    "    w = dict()\n",
    "    ni = dict()\n",
    "    for e, items in entity_items.items():\n",
    "        for i, wie in items.items():\n",
    "            add_to_vec(ni, i, wie * wie):\n",
    "            for j, wje in items.items():\n",
    "                add_to_mat(w, i, j, wie, wje)\n",
    "    for i, relate_items in w.items():\n",
    "        relate_items = {x: y/math.sqrt(ni[i] * ni[x]) for x, y in relate_items.items()}\n",
    "```\n",
    "\n",
    "得到物品的相似度之后，可以利用ItemCF算法的思想，给用户推荐和他历史上喜欢的物品内容相似的物品。\n",
    "\n",
    "如果用户的行为强烈受某一内容属性的影响，那么内容过滤算法在精度上有可能超过协同过滤算法。但强的内容特征不是所有物品都具有的，且需要丰富的领域知识才能获得，很多时候内容过滤算法的精度比协同过滤算法差。如果将这两种算法融合，能够获得比单独使用这两种算法更好的效果。\n",
    "\n",
    "向量空间模型在内容数据丰富时可以获得比较好的效果。如果文本很短，关键词很少，向量空间模型就很难计算出准确的相似度。\n",
    "\n",
    "另外，两篇文章的关键词虽然不同，但关键词所属的话题可能却是相同的。\n",
    "\n",
    "在这种情况下，首先需要知道文章的话题分布，然后才能准确地计算文章的相似度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org1ecf479\"></a>\n",
    "### LDA话题模型\n",
    "\n",
    "**如何建立文章、话题和关键词的关系是话题模型(topic model)研究的重点。**\n",
    "\n",
    "代表性的话题模型有LDA（Latent Dirichlet Allocation）<sup><a id=\"fnr.9\" class=\"footref\" href=\"#fn.9\">9</a></sup>。\n",
    "\n",
    "LDA作为一种生成模型，对一篇文档产生的过程进行了建模，其基本思想是，一个人在写一篇文章的时候，会首先想这篇文章要讨论哪些话题，然后思考这些话题用什么词描述，从而最终用词写成一篇文章。 **文章和词之间使用话题来联系的。**\n",
    "\n",
    "LDA有3种元素，即文档、话题和词语。每一篇文档都表现为词的集合，称为 **词袋模型（bag of words）** 。每个词在一篇文章中属于一个话题。\n",
    "\n",
    "令 $D$ 为文档集合， $D[i]$ 是第 $i$ 篇文档。 $w[i][j]$ 是第 $i$ 篇文档中的第 $j$ 个词。 $z[i][j]$ 是第 $i$ 篇文档中第 $j$ 个词属于的话题。\n",
    "\n",
    "LDA计算过程包括初始化和迭代两部分。首先对 $z$ 进行初始化，假设一共有 $K$ 个话题，对第 $i$ 篇文章中的第 $j$ 个词，可以随机给它赋予一个话题。用 $NWZ(w,z)$ 记录词 $w$ 被赋予话题 $z$ 的次数， $NZD(z,d)$ 记录文档 $d$ 中被赋予话题 $z$ 的词的个数。\n",
    "\n",
    "下面是伪代码：\n",
    "\n",
    "    foreach document i in range(0, |D|):\n",
    "        foreach word j in range(0, |D(i)|):\n",
    "            z[i][j] = rand() % K\n",
    "            NZD[z[i][j], D[i]]++\n",
    "            NWZ[w[i][j], z[i][j]]++\n",
    "            NZ[z[i][j]]++\n",
    "\n",
    "初始化之后，通过迭代使话题的分布收敛到一个合理的分布上去。伪代码如下：\n",
    "\n",
    "    while not converged:\n",
    "        foreach document i in range(0, |D|):\n",
    "            foreach word j in range(0, |D(i)|):\n",
    "                NWZ[w[i][j], z[i][j]]--\n",
    "                NZ[z[i][j]]--\n",
    "                NZD[z[i][j], D[i]]--\n",
    "                z[i][j] = SampleTopic()\n",
    "                NWZ[w[i][j], z[i][j]]++\n",
    "                NZ[z[i][j]]++\n",
    "                NZD[z[i][j], D[i]]++\n",
    "\n",
    "LDA可以很好地将词组合成不同的话题。<sup><a id=\"fnr.4\" class=\"footref\" href=\"#fn.4\">4</a></sup>\n",
    "\n",
    "使用LDA计算物品内容的相似度时，可以先计算出物品在话题上的分布，然后利用两个物品的话题分布计算物品的相似度。 **如果两个物品的话题分布相似，则认为两个物品具有较高的相似度，反之则认为两个物品的相似度较低。**\n",
    "\n",
    "计算分布的相似度可以利用KL散度<sup><a id=\"fnr.5\" class=\"footref\" href=\"#fn.5\">5</a></sup>\n",
    "\n",
    "\\begin{equation}\n",
    "D_{\\mathrm{KL}}(P\\|Q) = \\sum_i P(i) \\ln \\frac{P(i)}{Q(i)} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "其中 $P$ 和 $Q$ 是两个分布，KL散度越大说明分布的相似度越低。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org7150efd\"></a>\n",
    "\n",
    "## 发挥专家的作用\n",
    "\n",
    "对于既没有用户的行为数据，也没有充足的物品内容信息来计算准确的物品相似度的推荐系统，在建立时，为让用户得到比较好的体验，会选择利用专家进行标注。代表系统是个性化网络电台[Pandora](https://www.pandora.com/)和电影推荐网站[Jinni](http://www.jinni.com/)。\n",
    "\n",
    "Pandora雇用了一批懂计算机的音乐人进行了一项称为音乐基因的项目<sup><a id=\"fnr.6\" class=\"footref\" href=\"#fn.6\">6</a></sup>。其针对几万名歌手的歌的各个维度进行标注，使用了400多个特征<sup><a id=\"fnr.7\" class=\"footref\" href=\"#fn.7\">7</a></sup>（Pandora称这些特征为基因）。标注完所有的歌曲后，每首歌都可以表示为一个400维的向量，然后通过常见的向量相似度算法可以计算出歌曲的相似度。\n",
    "\n",
    "Jinni也利用与Pandora相似的想法设计了电影基因系统<sup><a id=\"fnr.8\" class=\"footref\" href=\"#fn.8\">8</a></sup>，让专家给电影进行标注。\n",
    "\n",
    "下面一些是针对电影的基因分类：\n",
    "\n",
    "-   **心情(Mood):** 表示用户观看电影的心情，比如幽默、兴奋。\n",
    "-   **剧情(Plot):** 包括电影剧情的标签。\n",
    "-   **类别(Genres):** 表示电影的类别，主要包括动画片、喜剧片、动作片等分类。\n",
    "-   **时间(Time/Period):** 电影故事发生的时间。\n",
    "-   **地点(Place):** 电影故事发生的地点。\n",
    "-   **观众(Audience):** 电影的主要观众群。\n",
    "-   **获奖(Praise):** 电影的获奖和评价情况。\n",
    "-   **风格(Style):** 功夫片、全明星阵容等。\n",
    "-   **态度(Attitudes):** 电影描述故事的态度。\n",
    "-   **画面(Look):** 电脑拍摄的画面技术，比如电脑动画。\n",
    "-   **标记(Flag):** 主要表示电影有没有暴力和色情内容。\n",
    "\n",
    "Jinni通过专家和机器学习相结合的方法解决了系统冷启动问题，其在电影基因工程中采用了半人工、半自动的方式。首先，它让专家对电影进行标记，每个电影都有大约50个基因，这些基因来自大约1000个基因库。然后，在专家标记一定的样本后，Jinni会使用自然语言理解和机器学习技术，通过分析用户对电影的评论和电影的一些内容属性对电影（特别是新电影）进行自己的标记。同时，Jinni也设计了让用户对基因进行反馈的界面，希望通过用户反馈不断改进电影基因系统。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## 脚注\n",
    "\n",
    "<sup><a id=\"fn.1\" class=\"footnum\" href=\"#fnr.1\">1</a></sup> 参见维基百科Vector Space Model词条。\n",
    "\n",
    "<sup><a id=\"fn.2\" class=\"footnum\" href=\"#fnr.2\">2</a></sup> 参考了解中文分词方法。\n",
    "\n",
    "<sup><a id=\"fn.3\" class=\"footnum\" href=\"#fnr.3\">3</a></sup> 参见<http://en.wikipedia.org/wiki/Tf–idf>。\n",
    "\n",
    "<sup><a id=\"fn.4\" class=\"footnum\" href=\"#fnr.4\">4</a></sup> 参考David M. Blei在其论文中的实验结果。参见David M. Blei、Andrew Y. Ng、Michael I. Jordan的“Latent dirichlet allocation”（Journal of Machine Learning Research 3，2003）\n",
    "\n",
    "<sup><a id=\"fn.5\" class=\"footnum\" href=\"#fnr.5\">5</a></sup> **KL散度** 是两个概率分布P和Q差别的非对称性的度量。具体参见<http://en.wikipedia.org/wiki/Kullback-Leibler_divergence>。\n",
    "\n",
    "<sup><a id=\"fn.6\" class=\"footnum\" href=\"#fnr.6\">6</a></sup> 参见“About The Music Genome Project”，地址为<https://www.pandora.com/about/mgp>。\n",
    "\n",
    "<sup><a id=\"fn.7\" class=\"footnum\" href=\"#fnr.7\">7</a></sup> 参见<https://en.wikipedia.org/wiki/Music_Genome_Project>及<http://wikibin.org/articles/list-of-music-genome-project-attributes.html>。\n",
    "\n",
    "<sup><a id=\"fn.8\" class=\"footnum\" href=\"#fnr.8\">8</a></sup> 参见<https://en.wikipedia.org/wiki/Jinni_(search_engine)>。\n",
    "\n",
    "<sup><a id=\"fn.9\" class=\"footnum\" href=\"#fnr.9\">9</a></sup> 中文翻译为**隐含狄利克雷分布**，参见<https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation>。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  },
  "name": "8-cold-start.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
